1. Field of the Invention
The present invention relates to a normalization processing technique used in arithmetic coding.
2. Description of the Related Art
Recently, H.264 has been standardized as a moving image compression coding method. This H.264 coding method requires a larger amount of computation as compared with known compression coding methods such as MPEG-2 and MPEG-4, but can achieve higher coding efficiency. In this H.264 coding method, the Context-based Adaptive Binary Arithmetic Coding (CABAC) method is defined as a variable length coding method (see, ITU-T H.264 “Advanced video coding for generic audiovisual services”).
In arithmetic coding, a symbol sequence is mapped between 0.0 and 1.0 on the number line, and its coordinates are coded into a codeword expressed in binary notation.
It is assumed that an occurrence probability of a symbol “1” is defined as “r”, an occurrence probability of a symbol “0” is defined as “1−r”, a range of the symbol sequence on the number line at the Ith point is defined as “codlRange”, and the minimum coordinates in the range are defined as “codlLow”. When an occurring symbol is the symbol “0”, codlRange and codlLow are updated as follows.codlRange=(1−r)*codlRangecodlLow=codlLow+r*codlRange
On the other hand, when an occurring symbol is the symbol “1”, codlRange and codlLow are updated as follows.codlRange=r*codlRangecodlLow=codlLow
As mapping is continuously repeated, the range codlRange becomes smaller. Accordingly, normalization processing is required to be performed so as to maintain computation accuracy.
A normalization process based on the CABAC method is illustrated in FIG. 2. The range on the number line codlRange, the minimum coordinates in the range codlLow, the number of non-output bits bitsOutStanding, and a flag indicating whether an output bit is the first bit of a slice firstBitFlag are input.
After the normalization process has been performed, the range on the number line codlRange, the minimum coordinates in the range codlLow, the number of non-output bits bitsOutStanding, the flag indicating whether an output bit is the first bit of a slice firstBitFlag, and a coded bit string are output.
In step S201, it is determined whether the value of codlRange is less than 0x100. If the value of codlRange is equal to or greater than 0x100, the normalization process ends. If the value of codlRange is less than 0x100, the process proceeds to step S202.
In step S202, it is determined whether the value of codlLow is less than 0x100. If the value of codlLow is less than 0x100, the process proceeds to step S204. In step 204, a function PutBit(0) to be described later is executed. Subsequently the process proceeds to step S208. On the other hand, if it is determined in step S202 that the value of codlLow is equal to or greater than 0x100, the process proceeds to step S203 in which it is determined whether the value of codlLow is equal to or greater than 0x200.
If the value of codlLow is less than 0x200, the process proceeds to step S205 in which 0x100 is subtracted from the value of codlLow.
Furthermore, the value of bitsOutStanding is incremented, and the process proceeds to step S208. On the other hand, if it is determined in step S203 that the value of codlLow is equal to or greater than 0x200, the process proceeds to step S206 in which 0x200 is subtracted from the value of codlLow. Subsequently, the process proceeds to step S207.
In step S207, a function PutBit(1) to be described later is executed. Subsequently, the process proceeds to step S208 in which the values of codlRange and codlLow are individually shifted to the left by one bit so as to obtain values each double the original value thereof. Subsequently, the process returns to step S201.
Next, a function PutBit(B) will be described with reference to FIG. 3. The value of an argument B is 0 (step S204) or 1 (step S207). In step S301, it is determined whether the value of firstBitFlag is not zero. If the value of firstBitFlag is not zero (i.e. firstBitFlag !=0 is true), the process proceeds to step S302. In step S302, the value of firstBitFlag is set to zero. Subsequently, the process proceeds to step S304. On the other hand, if it is determined in step S301 that the value of firstBitFlag is zero (i.e., firstBitFlag !=0 is false), the process proceeds to step S303. In step S303, one bit whose bit value is B is output. Subsequently, the process proceeds to step S304.
In step S304, it is determined whether the value of bitsOutStanding is greater than zero. If the value of bitsOutStanding is equal to or less than zero, the process ends. If the value of bitsOutStanding is greater than zero, the process proceeds to step S305. In step S305, one bit whose bit value is 1−B is output and the value of bitsOutStanding is decremented. The process then returns to step S304.
An example of a known normalization processing apparatus is illustrated in FIG. 10. A storage unit 1001 is a register array for storing the signals codlRange, codlLow, bitsOutStanding, and firstBitFlag and an output bit string. A determination device 1002 compares the value of the signal codlRange stored in the storage unit 1001 with 0x100.
If the value of the signal codlRange is equal to or greater than 0x100, the determination device 1002 transfers data stored in the storage unit 1001 to an output device 1004. If the value of the signal codlRange is less than 0x100, the determination device 1002 transfers the data stored in the storage unit 1001 to a bit string calculation device 1003.
The bit string calculation device 1003 is a circuit for performing the process from step S202 to step S208 in the flowchart illustrated in FIG. 2. The bit string calculation device 1003 calculates the values of the signals codlRange, codlLow, bitsOutStanding, and firstBitFlag, and transfers these calculation results and the output bit string to the storage unit 1001. As a result, the data stored in the storage unit 1001 is updated.
The output device 1004 is a circuit for externally outputting the signals codlRange, codlLow, bitsOutStanding, and firstBitFlag and the output bit string which have been transferred from the determination device 1002.
In the above-described known normalization process, however, each time the bit string calculation device 1003 doubles the value of the signal codlRange, the bit string calculation device 1003 is required to transfer the calculated value of the signal codlRange to the storage unit 1001 so as to cause the determination device 1002 to determine whether the process should be finished (end determination). Accordingly, the normalization process cannot be performed upon all pieces of corresponding data at the same time, and therefore coding and decoding cannot be performed rapidly.
For example, if the value of the signal codlRange is one, the update of data stored in the storage unit 1001 and the end determination performed by the determination device 1002 are repeated eight times. If the determination device 1002 is a circuit requiring one cycle for the end determination, eight cycles are required for the normalization process of all pieces of corresponding data.
On the other hand, a case can be considered in which output values corresponding to all of the signals codlRange, codlLow, firstBitFlag, and bitsOutStanding are prepared in advance in the form of a table. In this case, however, a large-capacity memory is required and a normalization processing apparatus including such a memory becomes more expensive.